package com.pan.common.algorithm.basic.sortbasic;

import org.apache.commons.lang3.ArrayUtils;

/**
 * @author by panstark
 * @description
 * @notice
 * @date 2020/12/21
 */
public class Insert2part {

    //{4,3,6,7,8,9,4,2,11,23,56,43,45}
    public static void insertSort(int[] arr){

        int length = arr.length;
        for(int i=0;i<length;i++){
            int temp = arr[i];
            int j=i;
            for(;j>0;j--){
                if(temp<arr[j-1]){
                    arr[j]=arr[j-1];
                }else{
                    break;
                }
            }
            arr[j]=temp;
        }
    }



    /**
     * 二分法排序<br>
     * 根据排序原则，每次我们都是在一个有序序列中插入一个新的数字<br>
     * 那么我们可以将这个有序序列进行二分。<br>
     * 左游标left为0，右游标right为i-1(i是这个数字在原数组中的位置)<br>
     * middle初始为。<br>
     * 当left<=right时<br>
     * middle是left和right的中值。<br>
     * 我们作如下操作。如果array[i]的值比array[middle]值大。<br>
     * 那么我们就移动左游标令值为middle+1<br>
     * 负责就移动右游标为middle-1<br>
     * 移动完成后,我们需要将i-1到left之间的值进行依次向后移动给array[i]空出一个位置然后将array[i]插入
     * <p style="color:red">时间复杂度n</p>
     */
    public static int[] binaryInsertSort(int[] array) {
        for (int i = 0; i < array.length; i++) {
            int temp = array[i];//待插入到前面有序序列的值
            int left = 0;//有序序列的左侧
            int right = i - 1;//有序序列的右侧
            int middle = 0;//有序序列的中间
            while (left <= right) {
                middle = (left + right) / 2;//赋值
                if (temp < array[middle]) {
                    right = middle - 1;
                } else {
                    left = middle + 1;
                }
            }
            for (int j = i - 1; j >= left; j--) {
                //从i-1到left依次向后移动一位,等待temp值插入
                array[j + 1] = array[j];
            }
            if (left != i) {
                array[left] = temp;
            }
        }
        return array;
    }



    public static void insertSort2part(int[] arr){

        int length = arr.length;
        for(int i=0;i<length;i++){
            int temp = arr[i];
            int index = insert(arr,0,i,temp);
            moveleft(arr,index,i);
            arr[index]=temp;
            System.out.println("--第"+i+"次坐标为:"+index);
            System.out.println("--第"+i+"次循环:"+ArrayUtils.toString(arr));

        }
    }

    private static int insert(int[] arr, int start,int end,int temp) {

        if(end-start<=0||end==0){
            return end;
        }

        int part = (start+end)/2;
        if(arr[part]==temp){
            return part;
        }

        int index = 0;
        if(arr[part]>temp){
            index= insert(arr,start,part,temp);
        }else if(arr[part]<temp){
            index=insert(arr,part+1,end,temp);
        }
        return index;
    }

    private static void moveleft(int[] arr,int index, int end) {
        for(int i=end;i>index&&i>0;i--){
            arr[i]=arr[i-1];
        }
    }


    public static void main(String[] args) {
        int[] arr ={4,3,6,7,8,9,4,2,11,23,56,43,45};
        //insertSort(arr);
        insertSort2part(arr);
        //binaryInsertSort(arr);
        System.out.println(ArrayUtils.toString(arr));
    }
}
